/*
 * $Id: LinkedList.h,v 1.3 2006-05-02 05:58:55 bacon Exp $
 */

#ifndef _XPP_BAS_LINKEDLIST_CLASS_
#define _XPP_BAS_LINKEDLIST_CLASS_

#include <xp/types.h>
#include <xp/macros.h>
#include <xp/bas/assert.h>
#include <xpp/bas/Link.h>
#include <xpp/bas/MemoryPool.h>
#include <xpp/bas/MemoryPoolable.h>

/*
 * CLASS: xpp::bas::LinkedList<T>
 *   A template class for double-linked list
 */
namespace xpp
{
	namespace bas
	{

		template <typename T> class LinkedList;
		template <typename T> class SortedLinkedList;

		template <typename T> 
		class LinkedListNode: protected DoubleLink, protected MemoryPoolable
		{
		public:
			friend class LinkedList<T>;
			friend class SortedLinkedList<T>;

			T value;
		
			LinkedListNode<T>* forward () 
			{
				return (LinkedListNode<T>*)link;
			}
			const LinkedListNode<T>* forward () const
			{
				return (const LinkedListNode<T>*)link;
			}

			LinkedListNode<T>* backward ()
			{
				return (LinkedListNode<T>*)back.link;
			}
			const LinkedListNode<T>* backward () const
			{
				return (const LinkedListNode<T>*)back.link;
			}

		protected:
			LinkedListNode () {}
			LinkedListNode (const T& v): value(v) {}

			void set_forward (const LinkedListNode<T>* node)
			{
				link = (Link*)node;
			}
			void set_backward (const LinkedListNode<T>* node)
			{
				back.link = (Link*)node;
			}
		};
		
		template <typename T> class LinkedList
		{
		public:
			typedef LinkedListNode<T> Node;

			enum 
			{
				INVALID_INDEX = ~(xp_size_t)0
			};
		
			LinkedList (xp_size_t mpb_size = 0): mp (xp_sizeof(Node), mpb_size)
			{
				this->node_count = 0;
				this->head_node = XP_NULL;
				this->tail_node = XP_NULL;
			}

			LinkedList (const LinkedList<T>& ll): mp (ll.mp.datumSize(), ll.mp.blockSize())
			{
				this->node_count = 0;
				this->head_node = XP_NULL;
				this->tail_node = XP_NULL;
				for (Node* p = ll.head_node; p != XP_NULL; p = p->forward()) {
				    append (p->value);
				}
			}
			~LinkedList () 
			{
				clearout ();
			}
			
			T& operator[] (xp_size_t index)
			{
				xp_assert (index < size());
				
				Node* p = head_node;
				while (index > 0) {
				    p = p->forward();
				    index--;
				}
				xp_assert (p != XP_NULL);
				return p->value;
			}

			const T& operator[] (xp_size_t index) const
			{
				xp_assert (index < size());
				
				Node* p = head_node;
				while (index > 0) {
				    p = p->forward();
				    index--;
				}
				xp_assert (p != XP_NULL);
				return p->value;
			}

			LinkedList<T>& operator= (const LinkedList<T>& ll) 
			{
				clear ();
				for (Node* p = ll.head_node; p != XP_NULL; p = p->forward())
				    append (p->value);
				return *this;
			}

			xp_size_t mpBlockSize() const
			{
				return this->mp.blockSize();
			}
		
			bool mpIsEnabled () const
			{
				return this->mp.isEnabled();
			}
		
			xp_size_t size () const 
			{
				return node_count;
			}

			int isEmpty () const 
			{
				return node_count == 0;
			}

			bool contains (const T& value) const
			{
			return nodeOf(value) != XP_NULL;    
			}
		
			Node* insertDatum (Node* node, const T& value);

			T& insert (Node* node, const T& value)
			{
				return insertDatum (node, value)->value;
			}

			T& insert (xp_size_t index, const T& value)
			{
				xp_assert (index <= node_count);

				if (index == node_count) return insert ((Node*)XP_NULL, value);

				register Node* np;
				register xp_size_t cnt;
				if (index < (node_count >> 1)) {
					for (np = head_node, cnt = 0;
					     cnt < index; np = np->forward(), cnt++) {
						xp_assert (np != XP_NULL);
					}
				}
				else {
					for (np = tail_node, cnt = node_count - 1;
					     cnt > index; np = np->backward(), cnt--) {
						xp_assert (np != XP_NULL);
					}
				}
				return insert (np, value);
			}

			T& prepend (const T& value)
			{
				return insert (head_node, value);
			}
			T& append (const T& value)
			{
				return insert ((Node*)XP_NULL, value);
			}

			Node* prependDatum (const T& value)
			{
				return insertDatum (head_node, value);
			}
			Node* appendDatum (const T& value)
			{
				return insertDatum ((Node*)XP_NULL, value);
			}

			void prependAll (const LinkedList<T>& list)
			{
				Node* n = list.tail_node;

				if (&list == this) {
					Node* head = list.head_node;
					while (n) {
						prepend (n->value);
						if (n == head) break;
						n = (Node*)n->back.link;
					}
				}
				else {
					while (n) {
						prepend (n->value);
						n = (Node*)n->back.link;
					}
				}
			}

			void appendAll (const LinkedList<T>& list) 
			{
				Node* n = list.head_node;
		
				if (&list == this)  {
					Node* tail = list.tail_node;
					while (n != XP_NULL) {
						append (n->value);
						if (n == tail) break;
						n = n->forward();
					}
				}
				else {
					while (n != XP_NULL) {
						append (n->value);
						n = n->forward();
					}
				}
			}
		
			void remove (Node* node);
			void remove (xp_size_t index) 
			{
				xp_assert (index < node_count);
		
				Node* np = head_node; 
				while (index > 0) {
					np = np->forward();
					index--;
				}
				remove (np);
			}

			int removeDatum (const T& value)
			{	
				Node* p = nodeOf (value);
				if (p == XP_NULL) return -1;
				remove (p);
				return 0;
			}

			int removeDatums (const T& value)
			{
				Node* p = nodeOf(value);
				if (p == XP_NULL) return -1;
				do {
					Node* tmp = p->forward();
					remove (p);
					p = nodeOf (value, tmp);
				} while (p != XP_NULL);
				return 0;
			}

			void removeHead ()
			{
				remove (head_node);
			}
			void removeTail ()
			{
				remove (tail_node);
			}
		
			Node* head () const 
			{
				return (Node*)head_node;
			}
			Node* tail () const 
			{
				return (Node*)tail_node;
			}
		
			Node* nodeAt (xp_size_t index) const
			{
				xp_assert (index < node_count);
				Node* p = head_node;
				while (index > 0) {
					p = p->forward();
					index--;
				}
				xp_assert (p != XP_NULL);
				return p;
			}

			Node* nodeOf (const T& value) const
			{
				for (Node* p = head_node; p != XP_NULL; p = p->forward()) {
					if (value == p->value) return p;
				}
				return XP_NULL;
			}
			Node* lastNodeOf (const T& value) const
			{
				for (Node* p = tail_node; p != XP_NULL; p = p->backward()) {
					if (value == p->value) return p;
				}
				return XP_NULL;
			}	

			Node* nodeOf (const T& value, Node* head) const
			{
				for (Node* p = head; p != XP_NULL; p = p->forward()) {
					if (value == p->value) return p;
				}
				return XP_NULL;
			}

			Node* lastNodeOf (const T& value, Node* tail) const
			{
				for (Node* p = tail; p != XP_NULL; p = p->backward()) {
					if (value == p->value) return p;
				}
				return XP_NULL;
			}	

			xp_size_t indexOf (const T& value) const
			{
				xp_size_t index = 0;
				for (Node* p = head_node; p != XP_NULL; p = p->forward()) {
					if (value == p->value) return index;
					index++;
				}
				return INVALID_INDEX;
			}
			xp_size_t lastIndexOf (const T& value) const
			{
				xp_size_t index = node_count;
				for (Node* p = tail_node; p != XP_NULL; p = p->backward()) {
					index--;
					if (value == p->value) return index;
				}
				return INVALID_INDEX;
			}

			T& get (xp_size_t index) 
			{
				xp_assert (index < node_count);
				Node* p = head_node;
				while (index > 0) {
					p = p->forward();
					index--;
				}
				xp_assert (p != XP_NULL);
				return p->value;
			}

			const T& get (xp_size_t index) const
			{
				xp_assert (index < node_count);
				Node* p = head_node;
				while (index > 0) {
					p = p->forward();
					index--;
				}
				xp_assert (p != XP_NULL);
				return p->value;
			}

			void set (xp_size_t index, const T& value)
			{
				xp_assert (index < node_count);

				Node* p = head_node;
				while (index > 0) {
					p = p->forward();
					index--;
				}
				xp_assert (p != XP_NULL);
				p->value = value;
			}
	
			void clear () 
			{
				Node* p, * saved;
		
				p = head_node;
				while (p) {
					saved = p->forward();
					
					if (mp.isDisabled()) delete p;
					else {
						p->~Node ();
					#if defined(_MSC_VER)
						p->operator delete (p, &mp);
					#else
						p->dispose (p, &mp);
					#endif
					}
					node_count--;
					p = saved;
				}

				head_node = tail_node = XP_NULL;
				xp_assert (node_count == 0);
			}

			void clearout ()
			{
				clear ();
				mp.dispose ();
			}
		
			typedef int (LinkedList<T>::*TraverseCallback) (Node* start, Node* cur);

			void traverse (TraverseCallback callback, Node* start)
			{
				Node* cur, * prev, * next;

				cur = start;
				while (cur != XP_NULL) 
				{
					prev = cur->backward();
					next = cur->forward();

					int n = (this->*callback) (start, cur);

					if (n > 0) cur = next;
					else if (n < 0) cur = prev;
					else break;
				}
			}

		protected:
			MemoryPool mp;
			Node*      head_node;
			Node*      tail_node;	
			xp_size_t  node_count;
		};
		
		template <typename T> 
		inline typename LinkedList<T>::Node* LinkedList<T>::insertDatum (
			Node* node, const T& value)
		{
			//Node* n = new(&mp) Node (value);
			Node* n = mp.isEnabled()? 
				(new(&mp) Node(value)): (new Node(value));

			if (node == XP_NULL) {
				if (node_count == 0) {
					head_node = tail_node = n;
				}	
				else {
					n->back.link = tail_node;
					tail_node->set_forward(n);
					tail_node = n;
				}
			}
			else {
				n->set_forward(node);
				n->set_backward(node->backward());
				if (node->back.link != XP_NULL)
					node->backward()->set_forward(n);
				else head_node = n;
				node->set_backward(n);
			}

			node_count++;
			return n;
		}

		template <typename T>
		inline void LinkedList<T>::remove (Node* node) 
		{
			xp_assert (node != XP_NULL && node_count > 0);
		
			if (node == head_node) {
				if (node_count == 1) {
					if (mp.isDisabled()) delete node;
					else {
						node->~Node ();
					#if defined(_MSC_VER)
						node->operator delete (node, &mp);
					#else
						node->dispose (node, &mp);
					#endif
					}
					head_node = tail_node = XP_NULL;
				}
				else {
					head_node = head_node->forward();
					head_node->set_backward (XP_NULL);
					if (mp.isDisabled()) delete node;
					else {
						node->~Node ();
					#if defined(_MSC_VER)
						node->operator delete (node, &mp);
					#else
						node->dispose (node, &mp);
					#endif
					}
				}
			}
			else if (node == tail_node) {
				if (node_count == 1) {
					if (mp.isDisabled()) delete node;
					else {
						node->~Node ();
					#if defined(_MSC_VER)
						node->operator delete (node, &mp);
					#else
						node->dispose (node, &mp);
					#endif
					}
					head_node = tail_node = XP_NULL;
				}
				else {
					tail_node = tail_node->backward();
					tail_node->set_forward (XP_NULL);
					if (mp.isDisabled()) delete node;
					else {
						node->~Node ();
					#if defined(_MSC_VER)
						node->operator delete (node, &mp);
					#else
						node->dispose (node, &mp);
					#endif
					}
				}
			}
			else {
				node->forward()->set_backward (node->backward());
				node->backward()->set_forward (node->forward());
				if (mp.isDisabled()) delete node;
				else {
					node->~Node ();
				#if defined(_MSC_VER)
					node->operator delete (node, &mp);
				#else
					node->dispose (node, &mp);
				#endif
				}
			}
		
			node_count--;
		}

	}
}

#endif


